// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-04 14:10
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class EraseOverlapIntervals {
    /**
     * 移除重叠的区间
     *
     * @param intervals
     * @return :返回重叠区间的数量
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        /*考虑方向: 区间左端点:
         *          区间右端点:
         *  区间如何是重叠的: a区间的右端点大于b区间的左端点 -> 朴素解法 -> 先排序再判断
         *
         * */
        int n = intervals.length;
        int ans = 0;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int rBorder = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (rBorder > intervals[i][0]) {
                ++ans;
            } else {
                rBorder = intervals[i][1];
            }
        }
        return ans;
    }

    @Test
    public void shout() {
        int[][] intervals = {{1, 2}, {5, 6}, {6, 8}, {7, 8}, {2, 3}, {3, 4}, {1, 3}};
        System.out.println(eraseOverlapIntervals(intervals));
    }

}
